package com.jonlandrum.selfbalancingtree;

import static org.hamcrest.CoreMatchers.instanceOf;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertThat;
import static org.junit.Assert.assertTrue;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

public class BinarySearchTreeTest {
    private BinarySearchTree<String> tree;
    
    @Before
    public void init() {
        tree = new BinarySearchTree<String>();
    }
    
    @After
    public void destroy() {
        tree = null;
    }
    
    @Test
    public void testConstructorNull() {
        assertThat(tree, instanceOf(BinarySearchTree.class));
    }
    
    @Test
    public void testConstructorString() {
        tree = new BinarySearchTree<String>("Root");
        assertThat(tree, instanceOf(BinarySearchTree.class));
    }
    
    @Test
    public void testConstructorNode() {
        Node<String> root = new Node<String>("Root");
        tree = new BinarySearchTree<String>(root);
        assertThat(tree, instanceOf(BinarySearchTree.class));
    }
    
    @Test
    public void testGetRootNull() {
        assertThat(tree.getRoot(), instanceOf(Node.class));
    }
    
    @Test
    public void testGetRootString() {
        tree.addElement("Root");
        assertThat(tree.getRoot(), instanceOf(Node.class));
    }
    
    @Test
    public void testGetRootNode() {
        Node<String> root = new Node<String>("Root");
        tree.addElement(root);
        assertThat(tree.getRoot(), instanceOf(Node.class));
    }
    
    @Test
    public void testGetNumElementsNull() {
        assertEquals(0, tree.getNumElements());
    }
    
    @Test
    public void testGetNumElements() {
        assertEquals(0, tree.getNumElements());
        tree.addElement("Root");
        assertEquals(1, tree.getNumElements());
    }
    
    @Test
    public void testHasRoot() {
        assertFalse(tree.hasRoot());
        tree.addElement("Root");
        assertTrue(tree.hasRoot());
    }
    
    @Test
    public void testHasElementString() {
        assertFalse(tree.hasElement("Root"));
        tree.addElement("Root");
        assertTrue(tree.hasElement("Root"));
        assertFalse(tree.hasElement("Child"));
    }
    
    @Test
    public void testHasElementNode() {
        Node<String> root = new Node<String>("Root");
        tree.addElement(root);
        assertTrue(tree.hasElement(root));
    }
    
    @Test
    public void testAddElementNull() {
        Node<String> child = new Node<String>();
        tree.addElement("Root");
        tree.addElement(child);
        assertFalse(tree.hasElement(child));
        assertEquals(1, tree.getNumElements());
    }
    
    @Test
    public void testAddElementString() {
        tree.addElement("Root");
        assertFalse(tree.hasElement("Child"));
        assertEquals(1, tree.getNumElements());
        tree.addElement("Child");
        assertTrue(tree.hasElement("Child"));
        assertEquals(2, tree.getNumElements());
    }
    
    @Test
    public void testAddElementNode() {
        tree.addElement("Root");
        Node<String> child = new Node<String>("Child");
        assertFalse(tree.hasElement(child));
        assertEquals(1, tree.getNumElements());
        tree.addElement(child);
        assertTrue(tree.hasElement(child));
        assertEquals(2, tree.getNumElements());
    }
    
    @Test
    public void testFindElementNull() {
        assertEquals(null, tree.findElement("Root").getData());
    }
    
    @Test
    public void testFindElementString() {
        tree.addElement("Root");
        assertEquals("Root", tree.findElement("Root").getData());
    }
    
    @Test
    public void testFindElementNode() {
        Node<String> child = new Node<String>("Child");
        tree.addElement(child);
        assertEquals(child.getData(), tree.findElement(child).getData());
    }
    
    @Test
    public void testRemoveElementNode() {
        Node<String> node = new Node<String>("Node");
        tree.addElement(node);
        assertTrue(tree.hasElement(node));
        assertEquals(1, tree.getNumElements());
        tree.removeElement(node);
        assertFalse(tree.hasElement(node));
        assertEquals(0, tree.getNumElements());
    }
    
    @Test
    public void testRemoveElementNotInCollection() {
        tree.addElement("Root");
        assertTrue(tree.hasElement("Root"));
        assertFalse(tree.hasElement("Child"));
        assertEquals(1, tree.getNumElements());
        tree.removeElement("Child");
        assertTrue(tree.hasElement("Root"));
        assertFalse(tree.hasElement("Child"));
        assertEquals(1, tree.getNumElements());
    }
    
    @Test
    public void testRemoveElementRootNoChildren() {
        BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
        tree.addElement(4);
        tree.removeElement(4);
        assertFalse(tree.hasElement(4));
        assertEquals(null, tree.getRoot().getData());
    }
    
    @Test
    public void testRemoveElementInternalNodeNoChildren() {
        BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
        tree.addElement(4);
        Node<Integer> node = new Node<Integer>(2);
        tree.addElement(node);
        node = tree.removeElement(node);
        assertEquals((Integer) 4, node.getData());
        assertFalse(tree.hasElement(2));
        assertEquals((Integer) 4, tree.getRoot().getData());
    }
    
    @Test
    public void testRemoveElementRootOneChild() {
        BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
        tree.addElement(4);
        tree.addElement(2);
        tree.removeElement(4);
        assertFalse(tree.hasElement(4));
        assertEquals((Integer) 2, tree.getRoot().getData());
    }
    
    @Test
    public void testRemoveElementInternalNodeOneChild() {
        BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
        tree.addElement(4);
        tree.addElement(2);
        tree.addElement(1);
        tree.removeElement(2);
        assertFalse(tree.hasElement(2));
        assertEquals((Integer) 4, tree.getRoot().getData());
        assertEquals((Integer) 1, tree.getRoot().getLeftChild().getData());
        assertEquals((Integer) 4, tree.getRoot().getLeftChild().getParent().getData());
    }
    
    @Test
    public void testRemoveElementRootTwoChildren() {
        BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
        tree.addElement(4);
        tree.addElement(2);
        tree.addElement(6);
        tree.removeElement(4);
        assertFalse(tree.hasElement(4));
        assertEquals((Integer) 6, tree.getRoot().getData());
        assertEquals((Integer) 2, tree.getRoot().getLeftChild().getData());
        assertEquals((Integer) 6, tree.getRoot().getLeftChild().getParent().getData());
    }
    
    @Test
    public void testRemoveElementInternalNodeTwoChildren() {
        BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
        tree.addElement(4);
        tree.addElement(2);
        tree.addElement(1);
        tree.addElement(3);
        tree.removeElement(2);
        assertFalse(tree.hasElement(2));
        assertEquals((Integer) 4, tree.getRoot().getData());
        assertEquals((Integer) 3, tree.getRoot().getLeftChild().getData());
        assertEquals((Integer) 4, tree.getRoot().getLeftChild().getParent().getData());
        assertEquals((Integer) 1, tree.getRoot().getLeftChild().getLeftChild().getData());
        assertEquals((Integer) 3, tree.getRoot().getLeftChild().getLeftChild().getParent().getData());
    }
    
    @Test
    public void testToString() {
        BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
        tree.addElement(4);
        tree.addElement(2);
        tree.addElement(1);
        tree.addElement(3);
        assertEquals("4\n2\n1\n3\n", tree.toString());
    }
}
